1. Field of the Invention
The invention generally relates to the field of computer graphics and, more particularly, to a system and method for generating run-length encoded raster data from spans.
2. Description of the Related Art
A raster is a computer representation of the colored pixels or dots of a picture or page, which may or may not be printed on some physical medium or displayed on a computer screen. A Page Description Language (PDL) is a means of describing a page or pages in terms of shapes and colors, rather than pixels. It is the job of a raster image processor to convert a page description expressed in a PDL into a raster.
Rasters may be stored in many different formats, such as:
(a) ‘pixel interleaved’, where the values for each colorant of a pixel are included in the raster before any of the values for colorants of subsequent pixels;
(b) ‘line interleaved’, where all the values for the colorants of one scanline of raster data are included before any of the colorants of the next scanline of raster data. Here, the values for each colorant of the line are grouped together;
(c) ‘band interleaved’, where color values for a single colorant of several consecutive lines are grouped together; and
(d) ‘frame interleaved’, where all the color values for each colorant of every pixel on the page appear before any values of the subsequent colorants.
It is also possible to store single colorants in separate files or separate areas of computer memory, i.e., in ‘separations’ that are sometimes used in printing.
Rasters may be compressed. This is sometimes achieved by treating the raster as a stream of bytes without using the knowledge that the content is a raster. Here, signal processing techniques are applied to the data independently of the representation.
Often, however, techniques that use knowledge about the nature of the raster data are employed. This saves space while still making it relatively easy to process the data. One such well-known technique is ‘run-length encoding’. Here, instead of expressing the color of each pixel individually, a common characteristic of rasters is exploited: that consecutive pixels often have the same color. Each line of a raster is comprised of a series of ‘runs’, where each run represents a sequence of pixels of the same color.
A ‘span’ is a run that is encoded as a color and a count of the number of Contiguous pixels sharing the color. Sometimes, a span may also contain a start position or pixel offset from the edge of the raster. This permits the omission of background spans, at the cost of the extra memory to store the position information. The inclusion of a position pixel or offset also permits representation of overlapping spans. Second and subsequent spans that overlap a first span would obliterate or mix with the shared pixels according to the painting model (discussed below). To utilize such a raster for display or printing requires the unique determination of the color of each pixel, and this requires the replacement of overlapping spans with non-overlapping spans. This process is known as ‘flattening’.
In addition to color information about an area of a raster, a span may also contain property information, such as the kind of halftone screening required, transparency information, trapping properties (particularly, which trapping zone the span falls in), and ‘hot spot’ information that identifies an area which, when selected by a user, would cause some desired action to occur.
Prior to addition of a new graphic shape to a raster (whether run-length encoded or not), it is decomposed into spans by a process known as ‘scan conversion’. The merging of these spans with a run-length encoded raster is substantially the same as flattening overlapping spans. Indeed, collecting overlapping spans from all shapes and then flattening them at the end is a useful technique in some situations.
Run-length encoding is applicable in either pixel interleaved form where the runs represent contiguous identical pixels, or line, band, frame, or separation interleaved where runs of similar values for individual colorants are separately encoded and boundaries of runs for the different colorants are not required to coincide.
An example of a run-length encoded format is the LW (Linework) and HC (High Resolution Continuous Tone) sub-parts of the TIFF/IT-P1 standard (ISO 12639:1998(E)).
Many page description languages specify that an opaque painting model will sometimes or always be used. Among these are the PostScript Language (PostScript Language Reference, second edition 1991 and third edition 1999, Addison-Wesley) and PDF (Portable Document Format Reference Manual, version 1.3, 1999 and version 1.4, 2001, Adobe Systems Incorporated), which are incorporated herein by reference.
In an opaque painting model, such as shown in FIG. 1(a), each shape that is applied by the page description to the page is defined such that anything that is previously painted in the same area of the raster is obliterated.
Other painting models permit the combination of the foreground shape with the background in a variety of ways. In the PostScript Language for example, the setoverprint operator can be used to indicate that only those colorants used to paint the shape will be obliterated in the background and other colorants of the same pixels are left unchanged, as shown in FIG. 1(b).
More complex painting models permit the foreground and the background to be mixed together in a variety of more general ways. This process is known as ‘compositing’.
Where a raster is not run-length encoded, it is sufficient to sequentially paint each span of a shape being applied into each pixel of the target raster. However, where a run-length raster is to be flattened or have new shapes applied to it then it is not straightforward or obvious how the run-length encoded background data should be adjusted efficiently. This is especially difficult when overprinting or generally compositing where a run that is entirely covered by another run cannot simply be removed, but must be split into separate runs of different colors.
U.S. Pat. No. 5,075,779 to Lefebvre et al. discloses a method for editing a run-length encoded raster. This, and other similar methods, can be characterized as ‘splicing’ new spans into old ones. Firstly, however, Lefebvre et al. only relates to single colorant rasters, and further suggests, line, band, frame, and separation interleaved rasters. Many algorithms for processing color require simultaneous access to all the colors of a pixel. A pixel interleaved (run-length encoded) raster is generally used to achieve such access.
Secondly, the method of Lefebvre et al. fails to disclose the processing of non-opaque painting models.
Thirdly, the method disclosed in Lefebvre et al., as well as others that employ linked structures to indicate the sequence of runs, is complicated and requires a significant amount of searching to locate the runs that are obscured or partially obscured by a newly introduced span.
U.S. Pat. No. 5,295,235 to Newman also discloses a method whereby a linked list is utilized to flatten spans. The method disclosed in Newman requires sorting of spans prior to flattening. When constructing a run-length encoded raster, the sorted list must then be processed from left to right, and a record kept of the spans at each pixel. The spans must be compared to determine which one should take precedence, and which one should terminate a span and start a new one. The spans must also be compared to determine when a span does not cover the pixel currently being considered. This entails a considerable amount of processing at each pixel, especially where numerous objects could contribute to the color of a pixel. This is a potentially expensive operation.
U.S. Pat. No. 5,377,023 to Sano et al. also discloses a method for processing run-length data. However, the starting point for the method disclosed is a run-length encoded raster, and not the spans with which it is constructed or modified.
U.S. Pat. No. 5,727,090 to Yellin is one of numerous patents that disclose variations on the way in which run-length data is represented for most efficient compression. Generally, such patents are not concerned with how the raster is constructed with or modified by overlapping spans; but rather how the run-length data is initially or finally packed.
It is therefore apparent that there is a need for a simpler method for advantageously flattening a run-length encoded raster such that searching, sorting and list manipulating are not required. It is also apparent that there is a need for a method to advantageously minimize the amount of memory required for such an operation.